//
// Created by Administrator on 2022/2/4.
//

#ifndef CPP_LEARNING_LEETCODE95_H
#define CPP_LEARNING_LEETCODE95_H
#include "treenode.h"
#include <vector>
using namespace std;
class Solution95 {
public:
    // [l,r]

    TreeNode* treeDeepCopy(TreeNode* node){
        if(node == nullptr){
            return nullptr;
        }
        TreeNode* newnode = new TreeNode();
        newnode->val = node->val;
        newnode->left = treeDeepCopy(node->left);
        newnode->right = treeDeepCopy(node->right);
        return newnode;
    }
    vector<TreeNode*> generateTreesHelper(int l, int r) {
        if(l > r) return vector<TreeNode*>{};
        if(l == r) return vector<TreeNode*>{new TreeNode(l)};

        vector<TreeNode*> trees;
        for(int i=l; i<=r; i++){
            vector<TreeNode*> leftTrees = generateTreesHelper(l,i-1);
            vector<TreeNode*> rightTrees = generateTreesHelper(i+1, r);


            if(leftTrees.size() > 0 && rightTrees.size() >0){
                for(int l=0; l<leftTrees.size(); l++){
                    for(int r=0;r < rightTrees.size(); r++){
                        TreeNode* node = new TreeNode(i);
                        node->left = leftTrees[l];
                        node->right = rightTrees[r];
                        trees.push_back(node);
                    }
                }
            }else if(leftTrees.size() > 0){
                for(int l=0; l<leftTrees.size(); l++){
                    TreeNode* node = new TreeNode(i);
                    node->left = leftTrees[l];
                    trees.push_back(node);
                }
            }else if(rightTrees.size() > 0){
                for(int r=0; r<rightTrees.size(); r++){
                    TreeNode* node = new TreeNode(i);
                    node->right = rightTrees[r];
                    trees.push_back(node);
                }
            }else{
                TreeNode* node = new TreeNode(i);
                trees.push_back(node);
            }
        }

        return trees;
    }

    vector<TreeNode*> generateTrees(int n) {
        return generateTreesHelper(1, n);
    }
};

void test95(){
    Solution95 s;
    vector<TreeNode*> trees = s.generateTrees(3);
    int a = 10;
}
#endif //CPP_LEARNING_LEETCODE95_H
